Psst... Ruszyły zawody olimpiady informatycznej dla uczniów szkół podstawowych i średnich. Zadania na tych konkursach są bardzo podobne do zadań, które rozwiązujesz, tutaj, na Szkopule.
Zobacz więcej:
- dla uczniów szkół podstawowych: oij.edu.pl/start/
- dla uczniów szkół średnich: oi.edu.pl/l/jak_zaczac/

Zadanie Zamieć (zam)

Zamieć

Limit pamięci: 128 MB

Nad Bajtołami Dolnymi przeszła zamieć. Ulice zostały pokryte wieloma metrami śniegu, a prognoza na najbliższe dni zapowiada mróz. Wszystko wskazuje na to, że jeszcze przez wiele dni mieszkańcy spędzą sporo czasu w swoich domach.

W tej sytuacji Bajtazar postanowił zająć się rozwiązywaniem następującego problemu algorytmicznego, który znalazł w Głosie Bajtołów. Dana jest macierz (tj. tabelka) liczb całkowitych. Należy znaleźć takie nienachodzących na siebie prostokątnych podtablic tej macierzy, że suma liczb w tych podtablicach jest jak największa. Każda z podtablic musi zawierać co najmniej jedną komórkę. Napisz program, który rozwiąże problem, z którym walczy Bajtazar.

Wejście

W pierwszym wierszu wejścia znajdują się trzy liczby całkowite , i (, ) oznaczające odpowiednio wysokość i szerokość macierzy oraz liczbę poszukiwanych podtablic. Kolejne wierszy opisuje poszczególne wiersze danej tablicy. Każdy z nich składa się z ciągu liczb całkowitych ().

Dodatkowo, w testach wartych łącznie punktów, .

Wyjście

Wypisz jedną liczbę całkowitą równą największej możliwej sumie liczb w

podtablicach podanej tablicy. Brzegi wybranych podtablic mogą się dotykać, jednak same podtablice nie mogą mieć wspólnych komórek.

Przykład

Dla danych wejściowych:

4 5 2
6 -10 0 3 -6
-8 8 1 -5 3
-7 -3 2 4 -4
2 0 -1 3 -3

poprawną odpowiedzią jest:

Zadanie zapożyczone z CPSPC 2010.